package com.hspedu.newData.力扣周赛.周赛.第450;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-18 
 * @Version: 1.0
 */

public class Q2数位和排序需要的最小交换次数 {

    static class MinIndex {
        int value, digitSum, index;

        MinIndex(int value, int index) {
            this.value = value;
            this.index = index;
            this.digitSum = check(value);
        }

        private int check(int num) {
            int sum = 0;
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
            return sum;
        }
    }

    public static int minSwaps(int[] nums) {
        int n = nums.length;

        // 1. 构建原数组带索引的对象数组
        MinIndex[] arr = new MinIndex[n];
        for (int i = 0; i < n; i++) {
            arr[i] = new MinIndex(nums[i], i);
        }

        // 2. 构建排序后的目标数组
        MinIndex[] sorted = arr.clone();
        Arrays.sort(sorted, (a, b) -> {
            if (a.digitSum != b.digitSum) {
                return a.digitSum - b.digitSum;
            } else {
                return a.value - b.value;
            }
        });

        // 3. 构建值到目标位置索引的映射
        Map<Integer, Integer> valueToTargetIndex = new HashMap<>();
        for (int i = 0; i < n; i++) {
            valueToTargetIndex.put(sorted[i].value, i);
        }

        // 4. 使用置换环统计最小交换次数
        boolean[] visited = new boolean[n];
        int swaps = 0;

        for (int i = 0; i < n; i++) {
            if (visited[i] || valueToTargetIndex.get(nums[i]) == i) {
                continue;
            }

            int cycleSize = 0;
            int j = i;

            while (!visited[j]) {
                visited[j] = true;
                int nextIndex = valueToTargetIndex.get(nums[j]);
                j = nextIndex;
                cycleSize++;
            }

            if (cycleSize > 1) {
                swaps += (cycleSize - 1);
            }
        }

        return swaps;
    }

    @Test
    public void test() {
        // 测试代码
        int i = minSwaps(new int[]{37,100});
        int j = minSwaps(new int[]{22,14,33,7});
        int l = minSwaps(new int[]{18,43,34,16});
        System.out.println("111");


    }
}
